package leetcode_周赛._2023._10;

/**
 * 第 367 场周赛 <p />
 * AC_3
 *
 * @author yezh
 * @date 2023/10/16 8:55
 */
public class _15 {

    public static void main(String[] args) {
        System.out.println(new _15().shortestBeautifulSubstring("100011001", 1));
    }

    /**
     * 2904.最短且字典序最小的美丽子字符串
     * 算法: 双指针
     */
    public String shortestBeautifulSubstring(String s, int k) {
        int len = s.length();
        String ans = "", t;
        for (int left = 0, right = 0, cnt1 = 0; right < len; ++right) {
            cnt1 += (s.charAt(right) - '0');
            while (cnt1 > k || (left < len && s.charAt(left) == '0')) cnt1 -= (s.charAt(left++) - '0');
            // 表示无解
            if (left >= len) break;
            if (cnt1 == k) {
                t = s.substring(left, right + 1);
                if ("".equals(ans) || t.length() < ans.length() || (t.length() == ans.length() && t.compareTo(ans) < 0)) ans = t;
            }
        }
        return ans;
    }

    String compare(String s, String ans) {
        int len1 = s.length(), len2 = ans.length();
        if (len1 != len2) return len1 < len2 ? s : ans;
        for (int i = 0; i < len1; i++) if (s.charAt(i) != ans.charAt(i)) return s.charAt(i) < ans.charAt(i) ? s : ans;
        return ans;
    }


    /**
     * 2905.找出满足差值条件的下标 II
     * 算法: 数学 + 脑筋急转弯
     */
    public int[] findIndices(int[] nums, int indexDifference, int valueDifference) {
        // 记录从后往前, 当前位置上的最大值和最小值
        // i + indexDifference
        // i - indexDifference
        int n = nums.length;
        for (int i = n - 1, minIdx = n - 1, maxIdx = n - 1; i >= indexDifference; i--) {
            if (nums[minIdx] > nums[i]) minIdx = i;
            if (nums[maxIdx] < nums[i]) maxIdx = i;
            int idx = i - indexDifference;
            if (Math.abs(nums[idx] - nums[minIdx]) >= valueDifference) return new int[]{idx, minIdx};
            if (Math.abs(nums[idx] - nums[maxIdx]) >= valueDifference) return new int[]{idx, maxIdx};
        }
        return new int[]{-1, -1};
    }

}
